LeetCode 239、滑动窗口最大值

一、题目描述

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 

解释:

提示：

• 你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

二、题目解析

滑动窗口这个词包含两个概念，一个是滑动，一个是窗口。

首先是窗口需要生成，一开始里面是没有任何元素的。

然后再滑动，随着窗口不断的滑动，窗口里面的元素个数从 0 到 1，再到 2，再到 3，此时，从窗口里面宣传最大值。

想要找出当前窗口里面的最大值，自然而然的想法就是遍历窗口中的所有元素，从中选出最大值，这样的复杂度是 O（k*n） 级别，复杂度有点高。

首先滑动窗口滑过所有的元素必然要经历 O(n) 的时间，这没法调整，所以可以优化的方向在于获取当前窗口的最大值，即想办法从 O(k) 优化到 O(logk）或者直接优化到 O(1)。

使用双端队列！

让窗口移动的过程，维护好队列里面的元素，做到每次窗口移动后都能马上知道当前窗口的最大值，由于想要做到 O(1) 的级别拿到最大值，那么必须是它的队首始终是最大值，也就是说我们需要维护一个递减队列用来保存队列中 所有递减的元素 。

一开始，窗口中只有 1，队列中放入 1。

窗口滑动，包含了 1 和 3，3 大于 1，如果直接放入队列，队列为 1 3，不是递减队列，所以需要先将 1 移除再放入 3 。

继续滑动，窗口元素为 1 3 -1 。

滑动窗口已经有三个元素，是合格的窗口，获取它的最大值只需要获取队列的队首元素就行。

同样的，窗口不断的向右移动，每次窗口都会增加新的元素，为了让队列中的队首元素始终是当前窗口的最大值，需要把队列中所有小于新元素值的那些元素移除。

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 滑动窗口最大值（ LeetCode 239 ）：https://leetcode-cn.com/problems/sliding-window-maximum/
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 边界情况
        if(nums.length == 0 || k == 0){
            return new int[0];
        }
        // 构建双端队列
        Deque<Integer> deque = new LinkedList<>();
        // 构建存储最大值的数组
        int[] res = new int[nums.length - k + 1];
        // 一开始滑动窗口不包含 K 个元素，不是合格的滑动窗口
        for(int i = 0; i < k; i++) {
            // 在滑动过程中，维护好 deque，确保它是单调递减队列

            // 反复判断，如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除。
            // 直到考察元素可以放入到队列中
            while(!deque.isEmpty() && deque.peekLast() < nums[i]){
                deque.removeLast();
            }

            // 考察元素可以放入到队列中
            deque.addLast(nums[i]);
        }
        // 这个时候，滑动窗口刚刚好有 k 个元素，是合格的滑动窗口，那么最大值就是队列中的队首元素
        res[0] = deque.peekFirst();


        // 现在让滑动窗口滑动
        for(int i = k; i < nums.length; i++) {
            // 滑动窗口已经装满了元素，向右移动会把窗口最左边的元素抛弃
            // i - k 为滑动窗口的最左边
            // 如果队列的队首元素和窗口最左边的元素相等，需要将队首元素抛出
            // 如果不写这个判断，会导致队列中会包含非当前窗口的元素
            // 比如窗口大小为 1，队列为 1 -1，此时窗口为 【 1 】,队列为 1，输出最大值 1，下一个窗口为 【 -1 】，准备移动的时候队列 1 和数组最左端元素一样，必须移除，否则队列中是 【 1，-1 】，输出的结果是 1，而 1 不在窗口 【 -1 】中
            if(deque.peekFirst() == nums[i - k]){
                deque.removeFirst();
            }
                

            // 反复判断，如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除。
            // 直到考察元素可以放入到队列中
            while(!deque.isEmpty() && deque.peekLast() < nums[i]){
                deque.removeLast();
            }
               
            // 考察元素可以放入到队列中
            deque.addLast(nums[i]);
            // 此时，结果数组的值就是队列的队首元素
            res[i - k + 1] = deque.peekFirst();
        }

        // 最后返回 res
        return res;
    }
}

**2、**C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 滑动窗口最大值（ LeetCode 239 ）：https://leetcode-cn.com/problems/sliding-window-maximum/
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        // 构建存储最大值的数组
        vector<int> res;

        if(nums.size() == 0 || k == 0){
            return res;
        }

        // 构建双端队列
        deque<int> deque;

        // 一开始滑动窗口不包含 K 个元素，不是合格的滑动窗口
        for(int i = 0; i < k; i++) {
            // 在滑动过程中，维护好 deque，确保它是单调递减队列

            // 反复判断，如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除。
            // 直到考察元素可以放入到队列中
            while(!deque.empty() && deque.back() < nums[i]){
                deque.pop_back();
            }
            // 考察元素可以放入到队列中
            deque.push_back(nums[i]);
        }
        // 这个时候，滑动窗口刚刚好有 k 个元素，是合格的滑动窗口，那么最大值就是队列中的队首元素
        res.push_back(deque.front());
        // 现在让滑动窗口滑动
        for(int i = k; i < nums.size(); i++) {
            // 滑动窗口已经装满了元素，向右移动会把窗口最左边的元素抛弃
            // i - k 为滑动窗口的最左边
            // 如果队列的队首元素和窗口最左边的元素相等，需要将队首元素抛出
            // 如果不写这个判断，会导致队列中会包含非当前窗口的元素
            // 比如窗口大小为 1，队列为 1 -1，此时窗口为 【 1 】,队列为 1，输出最大值 1，下一个窗口为 【 -1 】，准备移动的时候队列 1 和数组最左端元素一样，必须移除，否则队列中是 【 1，-1 】，输出的结果是 1，而 1 不在窗口 【 -1 】中
            if(deque.front() == nums[i - k]){
                deque.pop_front();
            }
            // 反复判断，如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除。
            // 直到考察元素可以放入到队列中
            while(!deque.empty() && deque.back() < nums[i]){
                deque.pop_back();
            }

            // 考察元素可以放入到队列中
            deque.push_back(nums[i]);
            // 此时，结果数组的值就是队列的队首元素
            res.push_back(deque.front());
        }
        // 最后返回 res
        return res;
    }
};

3、Python 代码 1

登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 滑动窗口最大值（ LeetCode 239 ）：https://leetcode-cn.com/problems/sliding-window-maximum/
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # 获取数组长度
        n = len(nums)
        # 构建双端队列
        q = collections.deque()
        # 建存储最大值的数组
        res = []

        # 边界情况
        if k < 1:
            return res
        # 一开始滑动窗口不包含 K 个元素，不是合格的滑动窗口
        for i in range (k):
            # 在滑动过程中，维护好 deque，确保它是单调递减队列

            # 反复判断，如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除。
            # 直到考察元素可以放入到队列中
            while q and q[-1] < nums[i]:
                q.pop()
            # 考察元素可以放入到队列中
            q.append(nums[i])

        # 这个时候，滑动窗口刚刚好有 k 个元素，是合格的滑动窗口，那么最大值就是队列中的队首元素
        res.append(q[0])

        # 现在让滑动窗口滑动
        for i in range (k, n):
            # 滑动窗口已经装满了元素，向右移动会把窗口最左边的元素抛弃
            # i - k 为滑动窗口的最左边
            # 如果队列的队首元素和窗口最左边的元素相等，需要将队首元素抛出
            # 如果不写这个判断，会导致队列中会包含非当前窗口的元素
            # 比如窗口大小为 1，队列为 1 -1，此时窗口为 【 1 】,队列为 1，输出最大值 1，下一个窗口为 【 -1 】，准备移动的时候队列 1 和数组最左端元素一样，必须移除，否则队列中是 【 1，-1 】，输出的结果是 1，而 1 不在窗口 【 -1 】中
            # while q and nums[q[-1]] <= nums[i]:
            #     q.pop()
            if q[0] == nums[i-k]:
                q.popleft()

            # 反复判断，如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除。
            # 直到考察元素可以放入到队列中
            while q and q[-1] < nums[i]: 
                q.pop()

            q.append(nums[i])

            # 考察元素可以放入到队列中
            res.append(q[0])
        # 最后返回 res
        return res

3、Python 代码 2

添加索引的方式

登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 滑动窗口最大值（ LeetCode 239 ）：https://leetcode-cn.com/problems/sliding-window-maximum/
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # 获取数组长度
        n = len(nums)
        # 构建双端队列，存储的是 nums 数组中元素的下标
        q = collections.deque()
        # 建存储最大值的数组
        res = []

        # 边界情况
        if k < 1:
            return res
        # 一开始滑动窗口不包含 K 个元素，不是合格的滑动窗口
        for i in range (k):
            # 在滑动过程中，维护好 deque，确保它是单调递减队列

            # 反复判断，如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除。
            # 直到考察元素可以放入到队列中
            # q[-1] 表示队尾元素下标，nums[q[-1]] 则是获取这个下标的元素
            while q and nums[i] >= nums[q[-1]]  :
                q.pop()

            # 考察元素的下标可以放入到队列中
            q.append(i)

        # 这个时候，滑动窗口刚刚好有 k 个元素，是合格的滑动窗口，那么最大值就是队列中的队首元素
        # q[-1] 表示队首元素下标，nums[q[0]] 则是获取这个下标的元素
        res.append(nums[q[0]])

        # 现在让滑动窗口滑动
        for i in range (k, n):
            # 滑动窗口已经装满了元素，向右移动会把窗口最左边的元素抛弃
            # i - k 为滑动窗口的最左边
            # 如果队列的队首元素和窗口最左边的元素相等，需要将队首元素抛出
            # 如果不写这个判断，会导致队列中会包含非当前窗口的元素
            # 比如窗口大小为 1，队列为 1 -1，此时窗口为 【 1 】,队列为 1，输出最大值 1，下一个窗口为 【 -1 】，准备移动的时候队列 1 和数组最左端元素一样，必须移除，否则队列中是 【 1，-1 】，输出的结果是 1，而 1 不在窗口 【 -1 】中
            # q 存储的是下标
            while q and q[0] <= i-k: 
                q.popleft()

            # 反复判断，如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除。
            # 直到考察元素可以放入到队列中
            while q and nums[q[-1]] <= nums[i]:
                q.pop()

            q.append(i)

            # 考察元素可以放入到队列中
            res.append(nums[q[0]])
        # 最后返回 res
        return res